package graph;

import linearList.SeqList;
import queue.LinkedQueue;

public class MatrixGraph<T> {
    // 最大权值，表示无穷大
    public static final int MAX_WEIGHT = 0x0000ffff;

    private SeqList<T> vertexList;
    private int[][] matrix;

    public static void main(String[] args) {
        /**
         *      带权无向图 (A,B,C,D,E)
         *
         *      0    45    28    10     ∞
         *     45     0    12     ∞    21
         *     28    12     0    17    26
         *     10     ∞    17     0    15
         *      ∞    21    26    15     0
         */
        String[] vertices = {"A", "B", "C", "D", "E"};
        Triple[] edges = {new Triple(0, 1, 45), new Triple(0, 2, 28), new Triple(0, 3, 10),
                new Triple(1, 0, 45), new Triple(1, 2, 12), new Triple(1, 4, 21),
                new Triple(2, 0, 28), new Triple(2, 1, 12), new Triple(2, 3, 17),
                new Triple(2,4,26),
                new Triple(3, 0, 10), new Triple(3, 2, 17), new Triple(3, 4, 15),
                new Triple(4, 1, 21), new Triple(4, 2, 26), new Triple(4, 3, 15)
        };

        MatrixGraph<String> graph = new MatrixGraph<>(vertices, edges);
        System.out.println("带权无向图G1，" + graph.toString());

        /**
         * 图遍历 有向图 (A,B,C,D,E)
         *
         *      0     1     ∞     1     1
         *      ∞     0     1     1     ∞
         *      ∞     ∞     0     ∞     1
         *      ∞     ∞     1     0     1
         *      ∞     ∞     ∞     ∞     0
         */
    }

    public MatrixGraph(int length) {
        this.vertexList = new SeqList<>(length);
        this.matrix = new int[length][length];
        initEgde();
    }

    public MatrixGraph(T[] vertices, Triple[] edges) {
        this.vertexList = new SeqList<>(vertices);
        this.matrix = new int[vertices.length][vertices.length];
        initEgde();

        for (Triple edge : edges) {
            this.insertEdge(edge);
        }
    }

    private void initEgde() {
        // 不同顶点之间的初始距离为无穷大，顶点和自身的距离为0
        int n = this.vertexList.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    this.matrix[i][j] = MAX_WEIGHT;
                }
            }
        }
    }

    public String toString() {
        String str = this.vertexList.toString() + "，邻接矩阵:  \n";
        int n = this.vertexList.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (this.matrix[i][j] == MAX_WEIGHT)
                    str += "     ∞";
                else str += String.format("%6d", this.matrix[i][j]);
            }
            str += "\n";
        }
        return str;
    }

    // 边
    public void insertEdge(int i, int j, int weight) {
        if (i != j) {
            this.matrix[i][j] = weight;
        }
    }

    public void insertEdge(Triple edge) {
        this.insertEdge(edge.row, edge.column, edge.value);
    }

    public void removeEdge(int i, int j) {
        if (i != j) {
            this.matrix[i][j] = MAX_WEIGHT;
        }
    }

    public void removeEdge(Triple edge) {
        this.removeEdge(edge.row, edge.column);
    }

    public int weight(int i, int j) {
        return this.matrix[i][j];
    }

    // 返回顶点vi在vj后的后继邻接顶点序号；
    // 若不存在后继邻接顶点，返回-1。
    private int next(int i, int j) {
        int n = this.vertexList.size();
        if (i >= 0 && i < n) {
            for (int k = j + 1; k < n; k++) {
                if (this.matrix[i][k] > 0 && this.matrix[i][k] < MAX_WEIGHT) {
                    return k;
                }
            }
        }
        return -1;
    }

    // 返回顶点vi的第一个邻接顶点序号
    // 若不存在，返回-1。
    private int first(int i) {
        int n = this.vertexList.size();
        if (i >= 0 && i < n) {
            for (int k = 0; k < n; k++) {
                if (this.matrix[i][k] > 0 && this.matrix[i][k] < MAX_WEIGHT) {
                    return k;
                }
            }
        }
        return -1;
    }

    //非连通图的一次广度优先搜索遍历，从顶点v0出发
    public void BFSTraverse() {
        System.out.println("广度优先搜索遍历 start.");
        boolean[] visited = new boolean[this.vertexList.size()];
        for (int i = 0; i < this.vertexList.size(); i++) {
            if (!visited[i]) {
                System.out.print("{ ");
                bfsTraverse(i, visited);
                System.out.print("} ");
            }
        }
        System.out.println("广度优先搜索遍历 end.");
    }

    //从顶点vi出发的一次广度优先搜索，遍历一个连通分量，使用队列
    private void bfsTraverse(int i, boolean[] visited) {
        // 访问节点
        System.out.print(this.vertexList.get(i) + " ");
        visited[i] = true;
        LinkedQueue<Integer> que = new LinkedQueue<Integer>();

        // 节点入队
        que.add(i);
        while (!que.isEmpty()) {
            i = que.poll();
            // 相邻节点访问->入队
            for (int j = first(i); j != -1; j = next(i, j)) {
                if (!visited[j]) {
                    System.out.print(this.vertexList.get(j) + " ");
                    visited[j] = true;
                    que.add(j);
                }
            }
        }
    }

    //非连通图的一次深度优先搜索遍历
    public void DFSTraverse() {
        System.out.println("深度优先搜索遍历 start.");
        boolean[] visited = new boolean[this.vertexList.size()];
        for (int i = 0; i < this.vertexList.size(); i++) {
            if (!visited[i]) {
                System.out.print("{ ");
                depthfs(i, visited);
                System.out.print("} ");
            }
        }
        System.out.println("深度优先搜索遍历 end.");
    }

    //从顶点vi出发的一次深度优先搜索，遍历一个连通分量；visited指定访问标记数组。递归算法
    private void depthfs(int i, boolean[] visited) {
        System.out.print(this.vertexList.get(i)+" ");
        visited[i] = true;
        // Vi所有邻接节点，深度优先遍历，递归调用
        for (int j=this.first(i); j!=-1; j=this.next(i,j)) {
            if(!visited[j]) {
                depthfs(j, visited);
            }
        }
    }
}